package main

import (
	"fmt"
	"sort"
)

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	o := make([][]int, 0)
	for i := 0; i < len(nums)-2; i++ {
		if nums[i] > 0 {
			break
		}

		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		base := 0 - nums[i]
		lo, hi := i+1, len(nums)-1
		for lo < hi {
			if nums[lo]+nums[hi] == base {
				o = append(o, []int{nums[i], nums[lo], nums[hi]})
				for lo < hi && nums[lo+1] == nums[lo] {
					lo++
				}
				for lo < hi && nums[hi-1] == nums[lo] {
					lo++
				}
				lo++
				hi--
			} else if nums[lo]+nums[hi] < base {
				lo++
			} else {
				hi--
			}
		}
	}
	return o
}

func main() {
	fmt.Println(threeSum([]int{-5, 2, 3, 6, -6}))
}
